import java.util.Arrays;

public class Recursion {
    //青蛙问题
    public static void main(String[] args) {
        System.out.print(fun8(1) + " ");
        System.out.print(fun8(2) + " ");
        System.out.print(fun8(3) + " ");
        System.out.print(fun8(4) + " ");
        System.out.print(fun8(5) + " ");
        System.out.print(fun8(6) + " ");
    }

    public static int fun8 (int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return fun8(n-1) +fun8(n-2);
    }


    //兔子问题
    public static void main7(String[] args) {
        System.out.print(fun7(1) + " ");
        System.out.print(fun7(2) + " ");
        System.out.print(fun7(3) + " ");
        System.out.print(fun7(4) + " ");
        System.out.print(fun7(5) + " ");
    }

    public static int fun7 (int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 0) {
            return 0;
        }
        return fun7(n -1) + fun7(n - 2);
    }



    //斐波那契
    public static void main6(String[] args) {
        System.out.print(fun6(1) +" ");
        System.out.print(fun6(2) +" ");
        System.out.print(fun6(3) +" ");
        System.out.print(fun6(4) +" ");
        System.out.print(fun6(5) +" ");
        System.out.print(fun6(6) +" ");
    }

    public static int fun6 (int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }

        return fun6(n-1) + fun6(n - 2);
    }


    // 插入排序
    public static void main5(String[] args) {
        int[] arr = {1,3,2,4,9,10,13};
        fun5(arr,1);
        System.out.println(Arrays.toString(arr));
    }

    public static void fun5 (int[] arr,int low) {
        if (low == arr.length) {
            return;
        }
        int temp = arr[low];
        int i = low - 1;
        while (arr[i] > temp) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = temp;
        fun5(arr,low + 1);
    }

    //冒泡排序升级版
    public static void main4(String[] args) {
        int[] arr = {1,3,2,4,9,10,13};
        fun4(arr, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void fun4 (int[] arr, int n) {
        if (n == 0) {
            return;
        }
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                j = i;
            }
        }
        fun4(arr,j);
    }

    //二分查找
    public static void main3(String[] args) {
        int[] arr = {1,3,5,7,9,10,13};
        System.out.println(fun3(arr, 0, arr.length - 1, 4));
    }
    public static int fun3 (int[] arr, int left, int right, int target) {
        int mid = (left + right) >>> 1;
        if (left > right) {
            return -1;
        }
        if(arr[mid] < target) {
            return fun3(arr, mid + 1,right,target);
        } else if (target < arr[mid]) {
            return fun3(arr,left,right - 1,target);
        }else {
            return mid;
        }
    }

    //反向打印字符串
    public static void main2(String[] args) {
        String str = "lisi";
        fun2(str,0);
    }
    public static void fun2 (String s, int n) {

        if (n == s.length()) {
            return;
        }
        fun2(s,n + 1);
        System.out.println(s.charAt(n));
    }


    //阶乘
    public static void main1(String[] args) {
        System.out.println(fun(5));
    }

    public static int fun(int n) {
        if (n == 1) {
            return 1;
        }
        return n * fun(n-1);
    }
}
